// 快排
//最好情况O(nlogn)
// 最差情况O(n*n)
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  const flag = arr[0]
  const left = []
  const right = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < flag) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), flag, ...quickSort(right)]
}
//
// let a = [4, 2, 1, 4, 4, 3, 5, 19, 12, 4]
// console.log(quickSort(a))

module.exports = function (arr){
  if (arr.length <= 1) {
    return arr
  }
  const flag = arr[0]
  const left = []
  const right = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < flag) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  tempArr =  [...quickSort(left), flag, ...quickSort(right)]
  return tempArr
}

